# -*- coding: utf-8 -*-

# n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
# 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案
# 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位

# 示例:
# 输入: 4
# 输出: [
#  [".Q..",  // 解法 1
#   "...Q",
#   "Q...",
#   "..Q."],

#  ["..Q.",  // 解法 2
#   "Q...",
#   "...Q",
#   ".Q.."]
# ]
# 解释: 4 皇后问题存在两个不同的解法
# 说明: 皇后的走法，皇后能横、竖、斜着走并且不限制步数








# # 解题思路以及错误：
# # 通过分析题目可以确定，当放置一个"Q"到棋盘上，会导致很多地方无法再放置"Q"，以此为基础进行解题
# # 1、由题目分析可得每一行都必须有一个"Q"，所以在0行的每一列放置1次"Q"就能遍历完成所有情况
# # 2、放置一个"Q"后，把所有不能再放置"Q"的位置都设置为"F"，然后再寻找下一个能放置"Q"的位置
# # ......
# # 3、全部遍历完成后检查棋盘上放置"Q"的数目，符合条件的保留下来
# # 
# # 未考虑到的情况:
# # 
# # n = 5 放置第一个元素后
# # Q F F F F
# # F F T T T
# # .........
# # 
# # 再放置第二个元素时，实际上是有3个候选位置[1][2] [1][3] [1][4]
# # 可是上面的算法只考虑了[1][2]这1中情况
# # 所以算法有漏洞不正确
# class Solution(object):
#     def solveNQueens(self, n):
#         """
#         :type n: int
#         :rtype: List[List[str]]
#         """
#         rtn = [];

#         # 在[row][col]上放置"Q"
#         def put_queen(row, col, checkerboard):
#             if not checkerboard[row][col]:
#                 return False;
#             checkerboard[row][col] = "Q";
#             for i in range(n):
#                 # 同行置为False
#                 if i != col:
#                     checkerboard[row][i] = False;

#                 # 同列置为False
#                 if i != row:
#                     checkerboard[i][col] = False;

#                 if i == 0:
#                     continue;

#                 # +45°斜线置为False
#                 if row + i < n and col + i < n:
#                     checkerboard[row + i][col + i] = False;
#                 if row - i >= 0 and col - i >= 0:
#                     checkerboard[row - i][col - i] = False;

#                 # -45°斜线置为False
#                 if row + i < n and col - i >= 0:
#                     checkerboard[row + i][col - i] = False;
#                 if row - i >= 0 and col + i < n:
#                     checkerboard[row - i][col + i] = False;
#             return True;

#         # 每行必有一个皇后，因此把第一个皇后放置在[0,n)开始推演

#         for col_first_queen in range(n):
#             checkerboard = [[True] * n for i in range(n)]
#             queen = 0;

#             # 放置第一行的Queen
#             put_queen(0, col_first_queen, checkerboard);
#             queen += 1;

#             # 依次放置其他Queen
#             for row in range(1, n):
#                 line = False;

#                 for col in range(n):
#                     if not checkerboard[row][col]:
#                         continue;

#                     line = True;
#                     queen += 1;

#                     put_queen(row, col, checkerboard);

#                 if not line:
#                     break;

#             if queen != n:
#                 continue;

#             for row in range(n):
#                 for col in range(n):
#                     if checkerboard[row][col] == "Q":
#                         continue;
#                     checkerboard[row][col] = ".";
#                 checkerboard[row] = "".join(checkerboard[row]);

#             rtn.append(checkerboard);

#         return rtn;






# 对此算法进行修正，通过上面问题的描述，此算法需要增加回溯的功能
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        rtn = [];

        # 在[row][col]设置"Q"时的约束修改
        def bound_queen(row, col, v):
            for i in range(n):
                # 同行置为False
                if i != col:
                    checkerboard[row][i] += v;

                # 同列置为False
                if i != row:
                    checkerboard[i][col] += v;

                if i == 0:
                    continue;

                # +45°斜线置为False
                if row + i < n and col + i < n:
                    checkerboard[row + i][col + i] += v;
                if row - i >= 0 and col - i >= 0:
                    checkerboard[row - i][col - i] += v;

                # -45°斜线置为False
                if row + i < n and col - i >= 0:
                    checkerboard[row + i][col - i] += v;
                if row - i >= 0 and col + i < n:
                    checkerboard[row - i][col + i] += v;

        def put_queen(row, col):
            if checkerboard[row][col] != 0:
                return False;
            checkerboard[row][col] = "Q";
            bound_queen(row, col, 1);
            return True;

        def remove_queen(row, col):
            if checkerboard[row][col] != "Q":
                return False;
            checkerboard[row][col] = 0;
            bound_queen(row, col, -1);
            return True;

        def add_solution():
            signal = [];
            for i in range(n):
                line = "";
                for j in range(n):
                    if checkerboard[i][j] == "Q":
                        line += "Q";
                    else:
                        line += ".";
                signal.append(line);
            rtn.append(signal);

        # 每行必有一个皇后，因此把第一个皇后放置在[0,n)开始推演
        def backtrack(row):
            for col in range(n):
                if not put_queen(row, col):
                    continue;
                if row + 1 == n:
                    add_solution();
                else:
                    backtrack(row + 1);
                remove_queen(row, col);

        checkerboard = [[0] * n for i in range(n)];
        backtrack(0);

        return rtn;




# # 解题思路：
# # 通过对问题分析可以得知 每一行必有一个"Q" 每一列必有一个"Q"
# # 以n=4为例
# # 预先设定行如下4中情况
# # "Q..."
# # ".Q.."
# # "..Q."
# # "...Q"
# # 这四种情况无论怎么组合都能满足 每一行必有一个"Q" 每一列必有一个"Q"
# # 而这四种情况的所有组合情况是一个全排列问题
# # 因此尝试建立 全排列 和 组合的对应关系
# # 分别记
# # "Q..." = 0 表示"Q"在第0列
# # ".Q.." = 1 表示"Q"在第1列
# # "..Q." = 2 表示"Q"在第2列
# # "...Q" = 3 表示"Q"在第3列
# # 
# # [1,3,0,2] 表示1在第0行，3在第1行，0在第2行，2在第3行
# # 即
# # ".Q.."
# # "...Q"
# # "Q..."
# # "..Q."
# # 通过上面的方法建立起全排列和棋盘的一一对应关系
# # 
# # 参见0046全排列的算法，求取全排列是1个元素1个元素确定的
# # 即[],[1],[1,3],[1,3,0],[1,3,0,2]这样依次确定的
# # 又因为上面的只处理了 同行 同列的问题，还有45°和-45°斜线的情况没有处理
# # 因而可以在新元素插入时检查是否在45°和-45°，如果在则已经不符合条件，直接跳出减少计算次数
# class Solution(object):
#     def solveNQueens(self, n):
#         """
#         :type n: int
#         :rtype: List[List[str]]
#         """
#         p_cols = [ i for i in range(n) ];
#         already = 0;

#         #p_cols中下标代指"Q"所在的行，值代指"Q"所在的列

#         def backtrack(index):
#             if index == n:
#                 arrays.append(p_cols[:]);
#                 return;

#             for i in range(index, n):
#                 is_available = True;

#                 for j in range(index):
#                     if index - j == abs(p_cols[i] - p_cols[j]):
#                         is_available = False;
#                         break;

#                 if not is_available:
#                     continue;

#                 p_cols[i], p_cols[index] = p_cols[index], p_cols[i];
#                 backtrack(index + 1);
#                 p_cols[i], p_cols[index] = p_cols[index], p_cols[i];

#         arrays = [];
#         backtrack(0);

#         template = [["."] * n for i in range(n)];
#         for i in range(n):
#             template[i][i] = "Q";
#             template[i] = "".join(template[i]);

#         for i in range(len(arrays)):
#             for j in range(len(arrays[i])):
#                 index = arrays[i][j];
#                 arrays[i][j] = template[index];

#         return arrays;

t = Solution();
print t.solveNQueens(5);